Plus fort ! - Olympiades 2023 Exercice 1

Dans tout ce problème,  \(n\) désigne un entier naturel supérieur ou égal à \(3\) .

Un joueur dispose de  \(n\) cartes numérotées de  \(1\) à \(n\) . Il les mélange puis note dans l’ordre la suite des numéros des cartes obtenue. On appelle liste la suite des numéros ainsi observés.

Le nombre  \(n\) sera appelé longueur de la liste.

Par exemple, avec \(n=8\) , une liste possible est \(L=[2,5,7,6,1,8,4,3]\) .

Avec une liste donnée, le joueur marque un point chaque fois que le numéro d’une carte est supérieur à celui de la carte précédente.

Par exemple avec la liste \(L=[2,\mathbf5,\mathbf7,6,1,\mathbf8,4,3]\) , le joueur marque  \(3\) points.

On appelle score le nombre de points marqués par le joueur. Le score précédent est donc \(3\) .

1. Quelques exemples
    a. Donner un autre exemple de liste de longueur  \(8\) et de score \(3\) .
    b. Donner toutes les listes de longueur  \(3\) possibles ainsi que les scores correspondants.

2. Écrire sur votre copie la syntaxe d’une fonction Python qui, prenant en argument une liste  \(L\) et sa longueur \(n\) , renvoie le score de la liste \(L\) .

On revient au cas général ainsi qu’à des considérations théoriques.

3. Démontrer que tout score est compris entre  \(0\) et \(n-1\) . Donner une liste dont le score vaut  \(0\) et une liste dont le score vaut \(n-1\) .

4. Soit  \(k\) un entier compris entre  \(1\) et \(n-2\) .
    a. Démontrer qu’il existe une liste de longueur  \(n\) et de score \(k\) .
    b. Peut-on trouver deux listes de longueur  \(n\) et de score  \(k\) ?

On note désormais  \(L_n(S)\) le nombre de listes de longueur  \(n\) et de score \(s\) .

5. Déterminer  \(L_n(0)\) et \(L_n(n-1)\) .

6. Une relation de récurrence
    a. Déterminer \(L_3(0)\) ,  \(L_3(1)\) et \(L_3(2)\) . Comment insérer dans la liste  \([3,1,2]\) la carte portant le numéro  \(4\) pour obtenir une liste dont le score vaut encore  \(1\) ?
    b. Comment insérer dans la liste  \([3,2,1]\) la carte portant le numéro  \(4\) pour obtenir une liste dont le score reste nul ?
   c. Vérifier que \(L_4(1)=2L_3(1)+3L_3(0)\) .
   d. Montrer que pour tout entier naturel \(n\ge3\) ,  \(\hspace{5 cm}L_{n+1}(1)=2L_n(1)+nL_n(0)\) .
   e. Pour tout  \(n\) et pour tout entier naturel  \(k\) non nul, exprimer  \(L_{n+1}(k)\) à l’aide de  \(L_n(k)\) et \(L_n(k-1)\) .
    f. Dresser un tableau des valeurs de  \(L_n(k)\) pour  \(n\in \{3,4,5\}\) et \(k\in\{0,1,2,3,4\}\) .